package 归并排序;

public class Solution327 {

    public static void main(String[] args) {
        int[] nums=new int[]{-2147483647,0,-2147483647,2147483647};
        int i = countRangeSum(nums, -564, 3864);
        System.out.println(i);
    }
    public static int countRangeSum(int[] nums, int lower, int upper) {

        return getSum(nums, lower, upper);
    }

    public static int getSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] sum = new int[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        return countSum(sum, 0, sum.length - 1, lower, upper);
    }

    //数组变成数组和
    public static int countSum(int[] nums, int l, int r, int lower, int upper) {

        //base case
        if (l == r) {
            if (nums[l] >= lower && nums[l] <= upper) {
                return 1;
            } else {
                return 0;
            }
        }
        int mid = (l + r) / 2;
        int left = countSum(nums, l, mid, lower, upper);
        int right = countSum(nums, mid + 1, r, lower, upper);
        int mer = merge(nums, l, mid, r, lower, upper);
        return left + right + mer;
    }

    public static int merge(int[] nums, int l, int mid, int r, int lower, int upper) {

        //不merge,找左组中，符合右组x-upper,x-lower

        int ans = 0;
        int windowL = l;
        int windowR = l;
        for (int i = mid + 1; i <= r; i++) {
            long min = nums[i] - upper;
            long max = nums[i] - lower;
            while (windowR <= mid && nums[windowR] <= max) {
                windowR++;
            }
            while (windowL <= mid && nums[windowL] < min) {
                windowL++;
            }
            ans = ans + windowR - windowL;
        }

        //正常merge
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;

        while (p1 <= mid && p2 <= r) {
            help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
        }
        while (p1 <= mid) {
            help[i++] = nums[p1++];
        }

        while (p2 <= r) {
            help[i++] = nums[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            nums[l + j] = help[j];
        }
        return ans;
    }
}
